<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script>
    //封装链表类
    function LinkedList(){
    //    内部类：节点类
        function Node(data){
            this.data = data
            this.next = null
        }

    //    属性
        this.head = null
        this.length = 0

    //    1、追加方法
        LinkedList.prototype.append = function(data){
        //1、创建新的节点
            var newNode = new Node(data)

        //2、判断是否添加的是一个第一个节点
            if(this.length == 0){ //2.1、 是第一个节点
                this.head = newNode
            }else{ //2.2、不是第一个节点
            //    找到最后的一个节点
                var current = this.head
                while(current.next){
                    current = current.next
                }

            //    最后节点的next指向新的节点
                current.next  = newNode
            }

        //    3、length+1
            this.length += 1
        }

    //    2、toSTring方法
        LinkedList.prototype.toString = function(){
        //    1、定义变量
            var current = this.head
            var listString = ""

        //    2、循环获取一个个节点
            while(current){
                listString += current.data + " "
                current = current.next
            }

            return listString
        }

    //    3、insert方法（在任意位置插入数据）
        LinkedList.prototype.insert = function(position,data){ //position:插入位置，data:插入内容
        //    1、对position进行越界判断
            if(position < 0 || position > this.length){
                return false
            }

        //    2、根据data创建newNode
            var newNode = new Node(data)

        //    3、判断插入位置是否是第一个
            if(position == 0){
                newNode.next = this.head
                this.head = newNode
            }else{
                var index = 0
                var current = this.head
                var previous = null
                while(index++ < position){
                    previous = current //previous指向current后一位元素
                    current = current.next
                }

                newNode.next = current
                previous.next = newNode
            }

        //    4、链表长度+1
            this.length += 1
            return true
        }

    //    4、get方法
        LinkedList.prototype.get = function(position){
        //    1、越界判断
            if(position < 0 || position >= this.length){
                return null
            }

        //    2、获取对应的data
            var current = this.head
            var index = 0
            while(index++ < position){
                current = current.next
            }

            return current.data
        }

    //    5、indexOf方法
        LinkedList.prototype.indexOf = function(data){
        //    1、定义变量
            var current = this.head
            var index = 0

        //    2、开始查找
            while(current){
                if(current.data == data){
                    return index
                }
                current = current.next
                index += 1
            }

        //    3、找到最后没有找到，返回-1
            return -1
        }

    //    6、update方法
        LinkedList.prototype.update = function(position,newData){
        //    1、越界判断
            if(position < 0 || position >= this.length) return false

        //    2、查找正确的节点
            var current = this.head
            var index = 0
            while(index++ < position){
                current = current.next
            }

        //    3、将position位置的node的data修改为newData
            current.data = newData

            return true
        }

    //    7、removeAt方法（删除指定位置节点）
        LinkedList.prototype.removeAt = function(position){
        //    1、越界判断
            if(position < 0 || position >= this.length) return null //越界则返回null

        //    2、判断是否为第一个节点
            var current = this.head
            if(position == 0){
                this.head = this.head.next
            }else{
                var index = 0
                var previous = null
                while(index++ < position){
                    previous = current
                    current = current.next
                }

            //  将被删除节点的前一个节点的next指向其后一个节点
            previous.next = current.next
            }

        //    3、链表长度-1
            this.length -= 1

            //删除成功返回删除节点的data
            return current.data
        }

    //    8、remove方法（根据data的内容删除节点）
        LinkedList.prototype.remove = function(data){ //    直接调用上面的indexOf和removeAt这两个封装方法
        //    1、使用indexOf方法找到内容为data的节点位置
            var position = this.indexOf(data)
        //    2、根据返回的节点位置删除节点
            this.removeAt(position)

            // 当内容为data的节点不存在时，position = -1，而remove(-1)返回的是null
        }

    //    9、isEmpty方法
        LinkedList.prototype.isEmpty = function(){
            return this.length == 0
        }

    //    10、size方法
        LinkedList.prototype.size = function(){
            return this.length
        }

    }
</script>
</body>
</html>